package ljl.alg.wangzheng_camp.round1.tree;

import java.util.*;

public class _590_ntree_postorder {
    
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    
    void dfs(Node root, List<Integer> res) {
        if (root == null)
            return;
        for (Node child : root.children) {
            dfs(child, res);
        }
        res.add(root.val);
    }
    
    /**
     * 方法二是，前序遍历改改，再逆序
     * 也很慢
     * */
    public List<Integer> postorder2(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == res) return null;
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (Node child : node.children) {
                stack.push(child);
            }
        }
        Collections.reverse(res);
        return res;
    }
    
    /**
     * 方法 3 是普通的迭代逆序
     *
     * 我直接抄了，不会写
     * */
    public List<Integer> postorder3(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        
        LinkedList<Node> stack = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.peek();
            if (node.children.size() == 0 || visited.contains(node)) {
                res.add(node.val);
                stack.pop();
                continue;
            }
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
            // 这个标记顺序很诡异，孩子先入栈，处理孩子；
            // 孩子全处理完，标记自己，下一把就处理自己
            // 我是想不到，你呢，老王（王八蛋）？
            visited.add(node);
        }
        return res;
    }
    
    /**
     * 有个精神病拿汇编模拟后序遍历...
     *
     * 这个怎么调，都是很慢
     * */
    /*
    * 0  if (root == null)
    * 1      return;
    * 2  for (Node child : root.children) {
    * 3      dfs(child, res);
    *    }
    * 4  res.add(root.val);
    * 5  return;
    * */
    class asm {
        class Pair{
            Node node; int index;
            Pair (Node node, int index) {this.node = node; this.index = index;}
        }
        class Frame {
            Pair data; int pc;
            Frame(Pair data, int pc) {this.data = data; this.pc = pc;}
        }
        public List<Integer> postorder(Node root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            
            Frame frame = new Frame(new Pair(root, 0), 0);
            Node ax = null;
            LinkedList<Frame> stack = new LinkedList<>();
            while (!stack.isEmpty() || frame.pc != 5) {
                switch (frame.pc) {
                    case 0 -> {
                        if (frame.data.node == null)
                            frame.pc = 1;
                        else
                            frame.pc = 2;
                    }
                    case 1 -> stack.pop();
                    case 2 -> {
                        if (frame.data.index == frame.data.node.children.size())
                            frame.pc = 4;
                        else {
                            ax = frame.data.node.children.get(frame.data.index);
                            frame.pc = 3;
                        }
                    }
                    case 3 -> {
                        frame.data.index++;
                        frame.pc = 2;
                        stack.push(frame);
                        frame = new Frame(new Pair(ax, 0), 0);
                    }
                    case 4 -> {
                        res.add(frame.data.node.val);
                        frame.pc = 5;
                    }
                    default -> frame = stack.pop();
                }
            }
            return res;
        }
    }
    
}
